package com.wanghe.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *  算法42. 接雨水
 *  https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class Problem42 {

    public static void main(String[] args) {

        int[] height = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
//        int[] height = new int[]{2,0,2};
        Problem42 p = new Problem42();
        System.out.println(p.trap(height));

    }

    public int trap(int[] height) {

        Stack<Integer> stack = new Stack<>();

        int index = -1;
        int volum = 0;
        for (int curHeight : height) {
            index++;
            if (stack.isEmpty() || curHeight <= height[stack.peek()]) {
                stack.push(index);
            } else {
                while (!stack.isEmpty() && height[stack.peek()] < curHeight) {
                    int top = stack.pop();
                    if (!stack.isEmpty()) {
                        int bar = Math.min(height[stack.peek()], curHeight);
                        volum += (bar - height[top]) * (index - stack.peek() - 1);
                    }
                }
                stack.push(index);
            }

        }
        return volum;
    }

}
